import sun.text.resources.no.CollationData_no;

import java.util.Arrays;
import java.util.Collections;

public class MergeSort {
    public static void main(String[] args) {
//        Collections.synchronizedList()
        int[] arr = {1,4,5,6,7,3,2,9,8};
        int left = 0;
        int right = arr.length -1 ;
        mergeSort(arr,left,right);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr,int left,int right) {
         if (left >= right){
             return;
         }
         int mid = (left + right) / 2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1, right);
        int[] tmp = new int[right - left + 1];
        int k = 0;
        int moveL = left;
        int moveR = mid + 1;
        while (moveL <= mid && moveR <= right){
            if (arr[moveL] > arr[moveR]){
                tmp[k++] = arr[moveR++];
            }else {
                tmp[k++] = arr[moveL++];
            }
        }
        while (moveL <= mid){
            tmp[k++] = arr[moveL++];
        }
        while (moveR <= right){
            tmp[k++] = arr[moveR++];
        }
        moveL = left;
        //拷贝回原数组
        for (int i = 0; i < tmp.length; i++) {
            arr[moveL++] = tmp[i];
        }
    }
}
